[译文] CFS 组调度

译者按：CFS 是 2.6.24 内核的一个亮点，自从 2.6.23 内核中引入 CFS 以来，又将有一次功能和性能的全面提升，这里分享一篇组调度相关的文章。

原文链接: http://lwn.net/Articles/240474/
[Posted July 2, 2007 by corbet]
译者：王旭
翻译时间：2008 年 1 月 28 日

Ingo Molnar 的完全公平调度器 (CFS) 补丁正在持续更新当中，本文写作时的版本是v18 ，翻译的时候的版本已经是v24了。不过，很多人都认为 CFS 的行为有一个极大的不足：它只在个体进程之间实现公平。如果50个进程想要同时运行，CFS 将小心行事，保障每个进程获得 2% 的 CPU。但是，这可能存在一个极端情况：这50个进程里有1个是 Alice 的 X server，而其余49个则是内核 hacker Karl 远程登陆过来，希望利用空闲空余的 CPU 时间加快内核编译过程的进程。如果 Karl 在系统中被真的公平地对待的话，应该让他的49个编译进程作为一个组来和 Alice 的 X server 来分享 CPU。换句话说，X 应该获得 50% 的 CPU（如果它需要的话），而所有的 Karl 的进程应该分享另外 50% 的 CPU。

上面提到的这种调度方式就称为“组调度”，Linux 中的任何一种调度器都还不能真正支持组调度。如果 CFS 在将来能被加入到内核当中，并且具备实现“组调度”的潜力，那将是一件很理想的事情。感谢 Srivatsa Vaddagiri 等人的工作，事情正在向着这个方向发展。

Srivatsa 的工作的第一部分已经进入了 CFS 补丁的 v17 版本了。它引入了一个称为“调度实体”的概念用以指代被调度的对象，这个对象不一定是一个进程。Srivatsa 保存了每个进程的调度信息，并将它们打包在一个 sched_entity 结构之中。这实际是一个简化，它封装了相关信息（实际要做的信息），同时也没有改变CFS 调度器的工作方式。

组调度实现为一组独立的补丁，目前还不是CFS代码的一部分。这些补丁将调度实体转换为一个层次结构。现在，调度实体并不和进程直接关联，相反，他们代表一组进程。每个调度实体内部有一个自己的运行队列。所有调度实体还有一个 parent 指针和一个指向调度它们的运行队列。

缺省地，进程都在顶级层次结构中，被单独地调度。一旦一个进程被移动到了一个调度实体下面，它就会在顶层运行队列里被删除。当进程可以运行的时候，它就被放到它的父调度实体对应的运行队列之中。

当调度起选择下一个要运行的任务的时候，它首先检查所有顶极调度实体，取出最应该获得CPU的任务。如果这个实体不是一个进程（而是一个高层调度实体），那么调度器就会检查调度实体中的运行队列，并重复这一过程，直到到达层次结构的最底层、找到一个进程，并运行这个进程。在进程运行时，同样会收集一些运行时统计信息，但这些信息同时会向上层调度实体传播，从而在每一级别上都正确度量其CPU占用。

这样，系统管理员可以为 Alice 和 Karl 各建立一个调度实体 。所有 Alice 的进程被放在她的调度实体之中，同样，Karl 的内核编译进程也放在他的调度实体里。CFS 调度器将保证 Alice 和Karl 之间的公平性；一旦调度器决定了谁应该获得 CPU，它将进入到下一级队列中，公平调度其中的用户进程。

队列的层次不一定按照用户来建立；进程可以被依照任何管理员觉得合适的方式来分组。分组可以更加粗略；比如，一个大学的计算机上，所有学生会被放到一个组里，教职员工放在另一个组中。层次化也可以是依照进程类型的：可以为系统守护进程、交互工具以及那些狂吃CPU的程序等各建立一个组。这个补丁中并不包括任何限制进程被如何分组的内容。

一个遗留问题可能是：系统管理员究竟怎么进行这个分组？答案在于组调度补丁的第二个部分，通过一个进程容器算法将调度实体组织在一起。管理员可以使用 cpuctl 参数来加载一个容器文件系统；调度组于是就可以在那个文件系统中以创建目录的方式被创建了。进程可以用容器界面来添加到（或移出）组。这样，任意特定的分组策略都可以利用一个简单的用户态守护程序来实现了，这个守护进程只要监视进程的创建事件，并将新建进程放到其应在的组里就可以了。

以目前的情况，容器代码只支持一层的组层次，而两级架构（如将用户分为管理员、故园和拜访者，然后对每个组里的用户们进行公平调度）还没有实现。这似乎是一个还没有被考虑到的限制，而不是一个代码中固有的问题。

有了组调度功能，CFS 将对相当一部分潜在用户更具吸引力。不过这些用户可能要等比较久了。2.6.23 的 merge window 很快就要开放了，不过那时这个补丁应该还没有完全准备好被加入到内核中去（译注：2.6.23 已经部分加入CFS了，不过更多的增强还是如作者所料在 2.6.24 中加入的）。可能 2.6.24 才会拥有那个值得期待的具有组调度功能的调度器。